package 题目集.dfs.洪水填充;


import 左哥算法.ch15并查集.UnionFindSet;

import java.util.*;

//https://pintia.cn/problem-sets/1728617645410041856/exam/problems/1728617696303685644?type=7&page=0
public class 肿瘤查找 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int l = sc.nextInt();
        int t = sc.nextInt();
        boolean[][][] maze = new boolean[l][m][n];
        for (boolean[][] booleans : maze) {
            for (boolean[] b : booleans) {
                for (int i = 0; i < b.length; i++) {
                    b[i] = sc.nextInt() == 1;
                }
            }
        }
        System.out.println(dfsFun(maze, t));
    }
    //试探方向
    static int[][] directions = {
            //下一层
            {-1, 0, 0},
            //当前层
            {0, 1, 0},
            {0, 0, 1},
            {0, -1, 0},
            {0, 0, -1},
            //下一层
            {1, 0, 0},
    };
//    static {
//        boolean [][][]maze={
//                {
//                        {true, false, true},
//                        {false, false, true},
//                        {true, false, true},
//                        {true, false, false},
//                }
//        };
//        int t=1;
//        System.out.println(fun(maze, t));
//    }

    static {
        int count=1000;
        Random random=new Random();
        while (count-- > 0) {
            int t=random.nextInt(10)+1;
            boolean[][][] maze=new boolean[random.nextInt(20)+1][random.nextInt(30)+1][random.nextInt(30)+1];
            boolean[][][] clone = new boolean[maze.length][maze[0].length][maze[0][0].length];
            for (int i = 0; i < maze.length; i++) {
                for (int j = maze[0].length - 1; j >= 0; j--) {
                    for (int k = 0; k < maze[0][0].length; k++) {
                        maze[i][j][k]=random.nextBoolean();
                        clone[i][j][k]=maze[i][j][k];
                    }
                }
            }
            long start,end;
            start=System.currentTimeMillis();
            int fun = fun(maze, t);
            end=System.currentTimeMillis();
            long time1=end-start;
            start=System.currentTimeMillis();
            int dfsFun=dfsFun(maze,t);
            end=System.currentTimeMillis();
            long time2=end-start;
            if (time2<time1){
                System.out.println(time2+"\t"+time1);
            }
            if (fun!=dfsFun){
                System.out.println("预期："+dfsFun+"\t实际："+fun+"\t t="+t);
                for (int i = 0; i < clone.length; i++) {
                    System.out.println(i+1);
                    for (int j = clone[0].length - 1; j >= 0; j--) {
                        System.out.println(Arrays.toString(clone[i][j]));
                    }
                }
                System.out.println("--------------------");
            }
        }
    }
    //试探方向
    public static int dfs(boolean[][][] maze, int z,int x,int y){
        if (z<0||z>=maze.length||x<0||x>=maze[0].length||y<0||y>=maze[0][0].length||!maze[z][x][y]){
            return 0;
        }
        int res=1;
        maze[z][x][y]=false;
        for (int[] d : directions) {
            res+=dfs(maze,z+d[0],x+d[1],y+d[2]);
        }
        return res;
    }
    public static int dfsFun(boolean[][][] maze,int t){
        int res=0;
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[0].length; j++) {
                for (int k = 0; k < maze[0][0].length; k++) {
                    int curr=dfs(maze,i,j,k);
                    res+=curr>=t?curr:0;
                }
            }
        }
        return res;
    }

    /**
     * true=肿瘤，false=非肿瘤
     */
    public static int fun(boolean[][][] maze, int t) {
        UnionFindSet<Node> unionSet = new UnionFindSet<>();
        Map<String, Node> map = new HashMap<>();
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[i].length; j++) {
                for (int k = 0; k < maze[i][j].length; k++) {
                    if (maze[i][j][k]) {
                        Node curr = map.getOrDefault(i + "," + j + "," + k, new Node(i, j, k));
                        map.put("" + i + j + k, curr);
                        unionSet.init(curr);
//                        Node curr=new Node(i,j,k);
                        for (int[] d : directions) {
//                            Node next=new Node(i+d[0],j+d[1],k+d[2]);
                            Node next = map.getOrDefault((i + d[0]) + "," + (j + d[1]) + "," + (k + d[2]), new Node(i + d[0], j + d[1], k + d[2]));
                            if (next.z < maze.length && next.z >= 0
                                    && next.x < maze[0].length && next.x >= 0
                                    && next.y < maze[0][0].length && next.y >= 0
                                    && maze[next.z][next.x][next.y]
                            ) {
                                unionSet.union(curr, next);
                            }
                        }
                    }
                }
            }
        }
        Collection<Integer> values = unionSet.getSizeMap().values();
        int res = 0;
        for (Integer v : values) {
            res += v >= t ? v : 0;
        }
        return res;
    }

    static class Node {
        int z;
        int x;
        int y;

        public Node(int z, int x, int y) {
            this.z = z;
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return z == node.z && x == node.x && y == node.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(z, x, y);
        }

        @Override
        public String toString() {
            return "Node{" +
                    "z=" + z +
                    ", x=" + x +
                    ", y=" + y +
                    '}';
        }
    }
}
